package com.zjsru.plan2023.oneday;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: CookLee
 * @Date: 2023/6/15
 * 构建回文串检测
 *
 * 输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
 * 输出：[true,false,false,true,true]
 * 解释：
 * queries[0] : 子串 = "d"，回文。
 * queries[1] : 子串 = "bc"，不是回文。
 * queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
 * queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
 * queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。
 *
 */
public class CanMakePaliQueries {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        List<Boolean> booleans = new ArrayList<>();
        int length = s.length();
        //将字符串转化为 只有 0或者1 的数组
        int[] counts = new int[length + 1];
        for (int i = 0; i < length; i++) {
            counts[i + 1] = counts[i] ^ (1 << (s.charAt(i) - 'a'));
        }
        //遍历回文串数组要求
        for (int i = 0; i < queries.length; i++) {
            //获取题干定义的三个参数
            int left = queries[i][0];
            int right = queries[i][1];
            int k = queries[i][2];
            //定义参数cnt 检测子串位数为1的个数
            int cnt = 0;
            //定义参数x:确定counts中从left 到 right中的 1 的个数
            int x = counts[right + 1] ^ counts[left];
            while(x > 0){
                //获取1的总数
                x &= x - 1;
                cnt++;
            }
            booleans.add(cnt <= 2 * k + 1);
        }
        return booleans;
    }
    
    public static void main(String[] args) {
        CanMakePaliQueries makePaliQueries = new CanMakePaliQueries();
        String s = "abcda";
        int[][] queries = new int[][] {{3, 3, 0}, {1, 2, 0}, {0, 3, 1}, {0, 3, 2}, {0, 4, 1}};
        System.out.println(makePaliQueries.canMakePaliQueries(s, queries));
    }
}
